package main.leetcode.clockin.April;

import java.util.*;

/**
 * 355.设计推特
 *
 * <p>设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：
 *
 * <p>postTweet(userId, tweetId): 创建一条新的推文 getNewsFeed(userId):
 * 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。 follow(followerId, followeeId): 关注一个用户
 * unfollow(followerId, followeeId): 取消关注一个用户
 *
 * <p>示例:
 *
 * <p>Twitter twitter = new Twitter();
 *
 * <p>// 用户1发送了一条新推文 (用户id = 1, 推文id = 5). twitter.postTweet(1, 5);
 *
 * <p>// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文. twitter.getNewsFeed(1);
 *
 * <p>// 用户1关注了用户2. twitter.follow(1, 2);
 *
 * <p>// 用户2发送了一个新推文 (推文id = 6). twitter.postTweet(2, 6);
 *
 * <p>// 用户1的获取推文应当返回一个列表，其中包含两个推文，id分别为 -> [6, 5]. // 推文id6应当在推文id5之前，因为它是在5之后发送的.
 * twitter.getNewsFeed(1);
 *
 * <p>// 用户1取消关注了用户2. twitter.unfollow(1, 2);
 *
 * <p>// 用户1的获取推文应当返回一个列表，其中包含一个id为5的推文. // 因为用户1已经不再关注用户2. twitter.getNewsFeed(1);
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/design-twitter
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class day13 {
    private static int timestamp = 0;
    private static PriorityQueue<Tweet> maxHeap;
    private HashMap<Integer, Tweet> tweets;
    private HashMap<Integer, HashSet<Integer>> followees;

    /** Initialize your data structure here. */
    public day13() {
        tweets = new HashMap<>();
        followees = new HashMap<>();
        maxHeap = new PriorityQueue<>((o1, o2) -> o2.timestamp - o1.timestamp);
    }

    public static void main(String[] args) {
        day13 twitter = new day13();
        twitter.postTweet(1, 5);
        System.out.println(twitter.getNewsFeed(1));
        twitter.follow(1, 2);
        twitter.postTweet(2, 6);
        System.out.println(twitter.getNewsFeed(1));
        twitter.unfollow(1, 2);
        System.out.println(twitter.getNewsFeed(1));
    }

    /** Compose a new tweet. */
    public void postTweet(int userId, int tweetId) {
        ++timestamp;
        Tweet head = tweets.get(userId);
        if (head == null) {
            head = new Tweet(tweetId, timestamp);
        } else {
            Tweet newHead = new Tweet(tweetId, timestamp);
            newHead.next = head;
            head = newHead;
        }
        tweets.put(userId, head);
    }

    /**
     * Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed
     * must be posted by users who the user followed or by the user herself. Tweets must be ordered
     * from most recent to least recent.
     */
    public List<Integer> getNewsFeed(int userId) {
        maxHeap.clear();

        // 加入自己的推文
        if (tweets.containsKey(userId)) {
            maxHeap.offer(tweets.get(userId));
        }

        // 加入关注列表的推文
        HashSet<Integer> hashSet = followees.get(userId);
        if (hashSet != null) {
            for (Integer fid : hashSet) {
                Tweet tweet = tweets.get(fid);
                if (tweet != null) {
                    maxHeap.offer(tweet);
                }
            }
        }

        // 根据大顶堆获取最近十条推文
        List<Integer> res = new ArrayList<>(10);
        Tweet head;
        for (int i = 0; !maxHeap.isEmpty() && i < 10; ++i) {
            head = maxHeap.poll();
            res.add(head.id);
            // 遍历所有推文
            if (head.next != null) {
                maxHeap.offer(head.next);
            }
        }
        return res;
    }

    /** Follower follows a followee. If the operation is invalid, it should be a no-op. */
    public void follow(int followerId, int followeeId) {
        if (followeeId == followerId) return;
        HashSet<Integer> hashSet = followees.get(followerId);
        if (hashSet == null) {
            hashSet = new HashSet<>();
        }
        hashSet.add(followeeId);
        followees.put(followerId, hashSet);
    }

    /** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
    public void unfollow(int followerId, int followeeId) {
        if (followeeId == followerId) return;
        HashSet<Integer> hashSet = followees.get(followerId);
        if (hashSet != null) {
            hashSet.remove(followeeId);
            followees.put(followerId, hashSet);
        }
    }

    private class Tweet {
        private int id;
        private int timestamp;
        private Tweet next;

        Tweet(int id, int timestamp) {
            this.id = id;
            this.timestamp = timestamp;
        }
    }
}

/**
 * Your Twitter object will be instantiated and called as such: Twitter obj = new Twitter();
 * obj.postTweet(userId,tweetId); List<Integer> param_2 = obj.getNewsFeed(userId);
 * obj.follow(followerId,followeeId); obj.unfollow(followerId,followeeId);
 */
